//给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
public class Partition {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
        public ListNode partition(ListNode pHead, int x) {
            ListNode cur = pHead;
            ListNode p1 = null;//小于x
            ListNode p2 = null;//大于x
            ListNode ret = null;//小于x的头
            ListNode srt = null;//大于x的头
            while (cur != null) {
                if (cur.val < x) {
                    if (p1 == null) {
                        p1 = cur;
                        ret = cur;//小于x的头
                    } else {
                        p1.next = cur;
                        p1 = p1.next;
                    }
                    cur = cur.next;
                } else {
                    if (p2 == null) {
                        p2 = cur;
                        srt = cur;
                    } else {
                        p2.next = cur;
                        p2 = p2.next;
                    }
                    cur = cur.next;
                }
            }
            if (ret == null) {//小于x的头
                return srt;
            }
            if (srt != null) {
                p2.next = null;

            }
            p1.next = srt;
            return ret;
        }
    }
